{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from prune import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 加载数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = load_data('ex2.txt')\n",
    "tree = create_tree(data, fleaf, ferr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 判断树结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "not_tree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 对树结构进行塌陷处理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "53.136107929136443"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "collapse(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 输出树结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'feat_idx': 0,\n",
       " 'feat_val': 0.50854200000000005,\n",
       " 'left': {'feat_idx': 0,\n",
       "  'feat_val': 0.46324100000000001,\n",
       "  'left': {'feat_idx': 0,\n",
       "   'feat_val': 0.13062599999999999,\n",
       "   'left': {'feat_idx': 0,\n",
       "    'feat_val': 0.085111000000000006,\n",
       "    'left': {'feat_idx': 0,\n",
       "     'feat_val': 0.053763999999999999,\n",
       "     'left': 4.0916259999999998,\n",
       "     'right': -2.5443927142857148},\n",
       "    'right': 6.5098432857142843},\n",
       "   'right': {'feat_idx': 0,\n",
       "    'feat_val': 0.37738300000000002,\n",
       "    'left': {'feat_idx': 0,\n",
       "     'feat_val': 0.3417,\n",
       "     'left': {'feat_idx': 0,\n",
       "      'feat_val': 0.32889000000000002,\n",
       "      'left': {'feat_idx': 0,\n",
       "       'feat_val': 0.30031799999999997,\n",
       "       'left': {'feat_idx': 0,\n",
       "        'feat_val': 0.17652300000000001,\n",
       "        'left': {'feat_idx': 0,\n",
       "         'feat_val': 0.156273,\n",
       "         'left': -6.2479000000000013,\n",
       "         'right': -12.107972500000001},\n",
       "        'right': {'feat_idx': 0,\n",
       "         'feat_val': 0.20399300000000001,\n",
       "         'left': 3.4496025000000001,\n",
       "         'right': {'feat_idx': 0,\n",
       "          'feat_val': 0.21832099999999999,\n",
       "          'left': -11.822278500000001,\n",
       "          'right': {'feat_idx': 0,\n",
       "           'feat_val': 0.228628,\n",
       "           'left': 6.770429,\n",
       "           'right': {'feat_idx': 0,\n",
       "            'feat_val': 0.26463900000000001,\n",
       "            'left': -13.070501,\n",
       "            'right': 0.40377471428571476}}}}},\n",
       "       'right': -19.994155200000002},\n",
       "      'right': 15.059290750000001},\n",
       "     'right': {'feat_idx': 0,\n",
       "      'feat_val': 0.35147800000000001,\n",
       "      'left': -22.693879600000002,\n",
       "      'right': -15.085111749999999}},\n",
       "    'right': {'feat_idx': 0,\n",
       "     'feat_val': 0.44619599999999998,\n",
       "     'left': {'feat_idx': 0,\n",
       "      'feat_val': 0.41894300000000001,\n",
       "      'left': {'feat_idx': 0,\n",
       "       'feat_val': 0.388789,\n",
       "       'left': 3.6584772500000016,\n",
       "       'right': -0.89235549999999952},\n",
       "      'right': 14.38417875},\n",
       "     'right': -12.558604833333334}}},\n",
       "  'right': {'feat_idx': 0,\n",
       "   'feat_val': 0.48380299999999998,\n",
       "   'left': 3.4331330000000007,\n",
       "   'right': 12.50675925}},\n",
       " 'right': {'feat_idx': 0,\n",
       "  'feat_val': 0.73163599999999995,\n",
       "  'left': {'feat_idx': 0,\n",
       "   'feat_val': 0.64237299999999997,\n",
       "   'left': {'feat_idx': 0,\n",
       "    'feat_val': 0.61886799999999997,\n",
       "    'left': {'feat_idx': 0,\n",
       "     'feat_val': 0.58541299999999996,\n",
       "     'left': {'feat_idx': 0,\n",
       "      'feat_val': 0.56030100000000005,\n",
       "      'left': {'feat_idx': 0,\n",
       "       'feat_val': 0.53194399999999997,\n",
       "       'left': 101.73699325000001,\n",
       "       'right': {'feat_idx': 0,\n",
       "        'feat_val': 0.546601,\n",
       "        'left': 110.979946,\n",
       "        'right': 109.38961049999999}},\n",
       "      'right': 97.200180249999988},\n",
       "     'right': 123.2101316},\n",
       "    'right': 93.673449714285724},\n",
       "   'right': {'feat_idx': 0,\n",
       "    'feat_val': 0.66785099999999997,\n",
       "    'left': 114.15162428571431,\n",
       "    'right': {'feat_idx': 0,\n",
       "     'feat_val': 0.70889000000000002,\n",
       "     'left': {'feat_idx': 0,\n",
       "      'feat_val': 0.69891999999999999,\n",
       "      'left': 108.92921799999999,\n",
       "      'right': 104.82495374999999},\n",
       "     'right': 114.554706}}},\n",
       "  'right': {'feat_idx': 0,\n",
       "   'feat_val': 0.95390200000000003,\n",
       "   'left': {'feat_idx': 0,\n",
       "    'feat_val': 0.76332800000000001,\n",
       "    'left': 78.085643250000004,\n",
       "    'right': {'feat_idx': 0,\n",
       "     'feat_val': 0.79819799999999996,\n",
       "     'left': 102.35780185714285,\n",
       "     'right': {'feat_idx': 0,\n",
       "      'feat_val': 0.83858699999999997,\n",
       "      'left': {'feat_idx': 0,\n",
       "       'feat_val': 0.81521500000000002,\n",
       "       'left': 88.784498800000009,\n",
       "       'right': 81.110151999999999},\n",
       "      'right': {'feat_idx': 0,\n",
       "       'feat_val': 0.94882200000000005,\n",
       "       'left': {'feat_idx': 0,\n",
       "        'feat_val': 0.85642099999999999,\n",
       "        'left': 95.275843166666661,\n",
       "        'right': {'feat_idx': 0,\n",
       "         'feat_val': 0.912161,\n",
       "         'left': {'feat_idx': 0,\n",
       "          'feat_val': 0.89668300000000001,\n",
       "          'left': {'feat_idx': 0,\n",
       "           'feat_val': 0.88361500000000004,\n",
       "           'left': 102.25234449999999,\n",
       "           'right': 95.181792999999999},\n",
       "          'right': 104.82540899999999},\n",
       "         'right': 96.452866999999998}},\n",
       "       'right': 87.310387500000004}}}},\n",
       "   'right': {'feat_idx': 0,\n",
       "    'feat_val': 0.96039799999999997,\n",
       "    'left': 112.42895575000001,\n",
       "    'right': 105.24862350000001}}}}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 使用测试数据进行后剪枝"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_test = load_data('ex2test.txt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "merged\n",
      "merged\n",
      "merged\n",
      "merged\n",
      "merged\n",
      "merged\n",
      "merged\n",
      "merged\n"
     ]
    }
   ],
   "source": [
    "pruned_tree = postprune(tree, data_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'feat_idx': 0,\n",
       " 'feat_val': 0.50854200000000005,\n",
       " 'left': {'feat_idx': 0,\n",
       "  'feat_val': 0.46324100000000001,\n",
       "  'left': {'feat_idx': 0,\n",
       "   'feat_val': 0.13062599999999999,\n",
       "   'left': {'feat_idx': 0,\n",
       "    'feat_val': 0.085111000000000006,\n",
       "    'left': 0.77361664285714249,\n",
       "    'right': 6.5098432857142843},\n",
       "   'right': {'feat_idx': 0,\n",
       "    'feat_val': 0.37738300000000002,\n",
       "    'left': {'feat_idx': 0,\n",
       "     'feat_val': 0.3417,\n",
       "     'left': {'feat_idx': 0,\n",
       "      'feat_val': 0.32889000000000002,\n",
       "      'left': {'feat_idx': 0,\n",
       "       'feat_val': 0.30031799999999997,\n",
       "       'left': {'feat_idx': 0,\n",
       "        'feat_val': 0.17652300000000001,\n",
       "        'left': -9.1779362500000019,\n",
       "        'right': {'feat_idx': 0,\n",
       "         'feat_val': 0.20399300000000001,\n",
       "         'left': 3.4496025000000001,\n",
       "         'right': {'feat_idx': 0,\n",
       "          'feat_val': 0.21832099999999999,\n",
       "          'left': -11.822278500000001,\n",
       "          'right': {'feat_idx': 0,\n",
       "           'feat_val': 0.228628,\n",
       "           'left': 6.770429,\n",
       "           'right': {'feat_idx': 0,\n",
       "            'feat_val': 0.26463900000000001,\n",
       "            'left': -13.070501,\n",
       "            'right': 0.40377471428571476}}}}},\n",
       "       'right': -19.994155200000002},\n",
       "      'right': 15.059290750000001},\n",
       "     'right': {'feat_idx': 0,\n",
       "      'feat_val': 0.35147800000000001,\n",
       "      'left': -22.693879600000002,\n",
       "      'right': -15.085111749999999}},\n",
       "    'right': {'feat_idx': 0,\n",
       "     'feat_val': 0.44619599999999998,\n",
       "     'left': {'feat_idx': 0,\n",
       "      'feat_val': 0.41894300000000001,\n",
       "      'left': 1.3830608750000011,\n",
       "      'right': 14.38417875},\n",
       "     'right': -12.558604833333334}}},\n",
       "  'right': {'feat_idx': 0,\n",
       "   'feat_val': 0.48380299999999998,\n",
       "   'left': 3.4331330000000007,\n",
       "   'right': 12.50675925}},\n",
       " 'right': {'feat_idx': 0,\n",
       "  'feat_val': 0.73163599999999995,\n",
       "  'left': {'feat_idx': 0,\n",
       "   'feat_val': 0.64237299999999997,\n",
       "   'left': {'feat_idx': 0,\n",
       "    'feat_val': 0.61886799999999997,\n",
       "    'left': {'feat_idx': 0,\n",
       "     'feat_val': 0.58541299999999996,\n",
       "     'left': {'feat_idx': 0,\n",
       "      'feat_val': 0.56030100000000005,\n",
       "      'left': {'feat_idx': 0,\n",
       "       'feat_val': 0.53194399999999997,\n",
       "       'left': 101.73699325000001,\n",
       "       'right': 110.18477824999999},\n",
       "      'right': 97.200180249999988},\n",
       "     'right': 123.2101316},\n",
       "    'right': 93.673449714285724},\n",
       "   'right': {'feat_idx': 0,\n",
       "    'feat_val': 0.66785099999999997,\n",
       "    'left': 114.15162428571431,\n",
       "    'right': {'feat_idx': 0,\n",
       "     'feat_val': 0.70889000000000002,\n",
       "     'left': 106.87708587499999,\n",
       "     'right': 114.554706}}},\n",
       "  'right': {'feat_idx': 0,\n",
       "   'feat_val': 0.95390200000000003,\n",
       "   'left': {'feat_idx': 0,\n",
       "    'feat_val': 0.76332800000000001,\n",
       "    'left': 78.085643250000004,\n",
       "    'right': {'feat_idx': 0,\n",
       "     'feat_val': 0.79819799999999996,\n",
       "     'left': 102.35780185714285,\n",
       "     'right': {'feat_idx': 0,\n",
       "      'feat_val': 0.83858699999999997,\n",
       "      'left': 84.947325400000011,\n",
       "      'right': {'feat_idx': 0,\n",
       "       'feat_val': 0.94882200000000005,\n",
       "       'left': {'feat_idx': 0,\n",
       "        'feat_val': 0.85642099999999999,\n",
       "        'left': 95.275843166666661,\n",
       "        'right': {'feat_idx': 0,\n",
       "         'feat_val': 0.912161,\n",
       "         'left': {'feat_idx': 0,\n",
       "          'feat_val': 0.89668300000000001,\n",
       "          'left': 98.717068749999996,\n",
       "          'right': 104.82540899999999},\n",
       "         'right': 96.452866999999998}},\n",
       "       'right': 87.310387500000004}}}},\n",
       "   'right': 108.838789625}}}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pruned_tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 生成树结构dot文件用于显示"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('ex2_prune.dot', 'w') as f:\n",
    "    content = dotify(pruned_tree)\n",
    "    f.write(content)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[1m\u001b[36m__pycache__\u001b[m\u001b[m/                 ex2test.txt\r\n",
      "\u001b[1m\u001b[36mdot\u001b[m\u001b[m/                         \u001b[1m\u001b[36mpic\u001b[m\u001b[m/\r\n",
      "ex0.txt                      prune.py\r\n",
      "ex00.txt                     regression_tree.py\r\n",
      "ex2.txt                      后剪枝.ipynb\r\n",
      "ex2_prune.dot                分段函数回归树.ipynb\r\n"
     ]
    }
   ],
   "source": [
    "ls"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
